In many occasions it is necessary to generate a sequence of data which are dependent on a basic key. A first field of application is to generate challenges which are identification numbers generated every ten seconds e.g. and requested in addition to a pin code. This number is only valid during a short time and avoids any replay from a third party. Such generator aims to replace the old strikethrough lists which were printed and sent to the user for the purpose of identification.
Another field of application is the generation of sub-keys in an encryption algorithm which uses multiple rounds. A first key should be then expanded to produce a lot of sub-keys, each of same being applied to one round. An example of such multiple rounds encryption method is described in the document U.S. Pat. No. 5,214,703.
We expect two characteristics of such a generation method, i.e. the non predictability of any of the other sequence (or the seed) while knowing one sequence and the reproduction of the sequence in either direction. This last characteristic is specifically used when the sequence is used as encryption sub-key since the decryption needs to use the sub-keys in reverse order.
A common solution is to apply the seed or the main key to a LFSR (Linear Feedback Shift Register). LFSR generators produce what are called linear recursive sequences (LRS) because all operations are linear. Generally speaking, the length of the sequence, before repetition occurs, depends upon two things, the feedback taps and the initial state. An LFSR of any given size m (number of registers) is capable of producing every possible state during the period N==2m−1, but will do so only if proper feedback taps, or terms, have been chosen. Such a sequence is called a maximal length sequence, maximal sequence, or less commonly, maximum length sequence.
Known methods use the output of such shift register to generate the sub-keys block by block to feed the rounds of the encryption process.
It is generally accepted that knowing one sequence generated that way opens the possibility to access to the other sequences or the seed.